#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cassert>

#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>

using namespace std;

#define PRODUCTION_MAX 512
#define ITEM_MAX 128
#define VN_MAX 128
#define VT_MAX 128
#define STRING_MAX 1024

#ifndef BEHCH_MARK_THREADS
  #define BEHCH_MARK_THREADS 16
#endif

/**
 * index the sorted productions and items
 * @ptr:    means the subscript of production[] or item[]
 * @length: means the same type size
**/
struct Index
{
  int ptr;
  int size;
  Index (): ptr(-1), size(0) { }
};

/**
 * record production like <0>::=<1><2>
 * @A:  <0>
 * @B:  <1>
 * @C:  <2>
**/
struct Production
{
  int A;
  int B;
  int C;
};

/**
 * record production like <0>::=<1>
 * @A:  <0>
 * @B:  <1>
**/
struct Item
{
  int A;
  char B;
};

struct ID
{
  int key;
  size_t l, r;
};

// index of Item by item.B
Index i_idx[VT_MAX];

// record production like <0>::=<1><2>
Production production[PRODUCTION_MAX];

// record item like <0>::=<1>
Item item[ITEM_MAX];

/**
 * dp[i][j][v] = n
 * There are n time of situation for string[i, j] to reduce to v
**/
unsigned int dp[STRING_MAX][STRING_MAX][VN_MAX];

ID ids[BEHCH_MARK_THREADS + 1];
pthread_t pids[BEHCH_MARK_THREADS + 1];

sem_t sems[STRING_MAX][STRING_MAX];

int vn_num;
int production_num;
int item_num;
int string_length;
char str[STRING_MAX];

void* node(void *arg);
ID next_to(ID id, size_t size, size_t step);
bool in(ID id);

int main(int argc, char **argv)
{
  // basic io
  if (argc != 2)
  { printf ("cyk <input.txt>"); return 0; }

  freopen(argv[1], "r", stdin);
  scanf("%d\n", &vn_num); scanf("%d\n", &production_num);
  for (int i = 0; i < production_num; i++)
    scanf("<%d>::=<%d><%d>\n", &production[i].A, &production[i].B, &production[i].C);
  scanf("%d\n", &item_num);
  for (int i = 0; i < item_num; i++)
    scanf("<%d>::=%c\n", &item[i].A, &item[i].B);
  scanf("%d\n", &string_length); scanf("%s\n", str);

  // sort ascending order by item.B and item.A
  sort (item, item + item_num, [](const Item& a,
                                  const Item& b)
  { return a.B == b.B ? a.A < b.A : a.B < b.B; });

  // init the index which indexed by [item.B]
  for (int i = 0; i < item_num; i++)
  {
    int t = item[i].B;
    if (i_idx[t].ptr == -1) i_idx[t].ptr = i;
    i_idx[t].size++;
  }

  for (int i = 1; i < string_length; i++)
    for (int j = i; j < string_length; j++)
      sem_init (&sems[i][j], 0, 0);

  for (int i = 0; i < string_length; i++)
    sem_init (&sems[i][i], 0, 2);

  // compute len is 1 situation
  for (int i = 0; i < string_length; i++)
  {
    int t = str[i];
    for (int j = i_idx[t].ptr; j < i_idx[t].ptr + i_idx[t].size; j++)
      dp[i][i][item[j].A] = 1;
  }

  // compute len in [2, string_length] situation
  ids[0] = {0, 0, 1};
  for (int i = 0; i < BEHCH_MARK_THREADS; i++)
  {
    int err = pthread_create (&pids[i], NULL, &node, &ids[i]);
    printf ("create %d at [%ld, %ld]\n", ids[i].key, ids[i].l, ids[i].r);
    if (err != 0) perror ("138");
    ids[i + 1] = next_to (ids[i], string_length, 1);
    ids[i + 1].key = ids[i].key + 1;
  }
  for (int i = 0; i < BEHCH_MARK_THREADS; i++)
  {
    // if (i + 1 == (string_length * (string_length - 1) / 2) % BEHCH_MARK_THREADS)
    {
      // printf ("main is waiting %d...\n", ids[i].key);
      pthread_join (pids[i], NULL);
    }
  }

  for (int i = 0; i < string_length; i++)
    for (int j = i; j < string_length; j++)
      sem_destroy (&sems[i][j]);

  printf("res = %u\n", dp[0][string_length - 1][0]);
  return 0;
}

inline ID next_to(ID id, size_t size, size_t step)
{
  while (step--)
  {
    id.l++, id.r++;
    if (id.r == size)
      id.r = size - id.l + 1, id.l = 0;
  }
  return {id.key, id.l, id.r};
}

inline bool in(ID id)
{
  return id.l < (size_t)string_length && id.r < (size_t)string_length;
}

void* node(void *arg)
{
  assert (arg != NULL);
  ID id = {((ID *)arg)->key, ((ID *)arg)->l, ((ID *)arg)->r};
  if (!in(id))
    pthread_exit (NULL);
  while (true)
  {
printf("%d is waiting [%ld, %ld] & [%ld, %ld]...\n", id.key, id.l, id.r - 1, id.l + 1, id.r);
    sem_wait (&sems[id.l][id.r - 1]);
    sem_wait (&sems[id.l + 1][id.r]);
printf ("%d todo: %ld=[%ld, %ld]\n", id.key, id.r - id.l + 1, id.l, id.r);
    for (size_t mid = id.l + 1; mid <= id.r; mid++)
    {
      for (int p = 0; p < production_num; p++)
      {
        dp[id.l][id.r][production[p].A]
          += dp[id.l][mid - 1][production[p].B] 
          * dp[mid][id.r][production[p].C];
      }
    }
printf ("%d done: %ld=[%ld, %ld]\n", id.key, id.r - id.l + 1, id.l, id.r);
    sem_post (&sems[id.l][id.r]);
    sem_post (&sems[id.l][id.r]);
    id = next_to (id, string_length, BEHCH_MARK_THREADS);
    if (!in(id)) break;
  }
  pthread_exit (NULL);
}